package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * 2370. 最长理想子序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/8 16:17
 */
public class LongestIdealString {

    public static void main(String[] args) {
        LongestIdealString test = new LongestIdealString();

        // 4
//        String str = "acfgbd";
//        int k = 2;

        // 4
        String str = "aecd";
        int k = 4;

        int i = test.longestIdealString(str, k);
        System.out.println(i);

    }

    public int longestIdealString(String s, int k) {
        int[] arr = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            int c = s.charAt(i) - 'a';
            int st = Math.max(c - k, 0);
            int end = Math.min(c + k, 25);
            int m = 0;
            for (int j = st; j <= end; j++) {
                m = Math.max(m, arr[j]);
            }
            arr[c] = m + 1;
        }
        int max = 0;
        for (int i : arr) {
            max = Math.max(max, i);
        }
        return max;
    }

}
